package com.ruijixiang.leetcode.weekly.leetcode2025.leetcode20250302;

public class LeetCode3474 {
    public String generateString(String str1,String str2){
        int n = str1.length();
        int m = str2.length();
        int totalLength = n + m - 1;
        if (totalLength < m) {
            return "";
        }

        char[] required = new char[totalLength];
        // Preprocess all 'T' conditions
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'T') {
                for (int t = 0; t < m; t++) {
                    int pos = i + t;
                    if (pos >= totalLength) {
                        return "";
                    }
                    if (required[pos] != '\0' && required[pos] != str2.charAt(t)) {
                        return "";
                    }
                    required[pos] = str2.charAt(t);
                }
            }
        }

        // Check all 'F' conditions for potential violations
        for (int i = 0; i < n; i++) {
            if (str1.charAt(i) == 'F') {
                boolean isFixed = true;
                for (int t = 0; t < m; t++) {
                    int pos = i + t;
                    if (pos >= totalLength) {
                        isFixed = false;
                        break;
                    }
                    if (required[pos] == '\0') {
                        isFixed = false;
                        break;
                    }
                    if (required[pos] != str2.charAt(t)) {
                        isFixed = false;
                        break;
                    }
                }
                if (isFixed) {
                    return "";
                }
            }
        }

        // Initialize result array with required characters
        char[] result = required.clone();

        // Fill remaining positions to achieve lex smallest string
        for (int pos = 0; pos < totalLength; pos++) {
            if (result[pos] != '\0') {
                continue;
            }
            for (char c = 'a'; c <= 'z'; c++) {
                boolean valid = true;
                // Check all relevant 'F' constraints
                for (int i = 0; i < n; i++) {
                    if (str1.charAt(i) != 'F') continue;
                    if (!(i <= pos && i + m - 1 >= pos)) continue;

                    boolean currentEquals = true;
                    for (int t = 0; t < m; t++) {
                        int j = i + t;
                        if (j >= totalLength) {
                            currentEquals = false;
                            break;
                        }
                        if (j == pos) {
                            if (c != str2.charAt(t)) {
                                currentEquals = false;
                                break;
                            }
                        } else {
                            if (result[j] == '\0') {
                                currentEquals = false;
                                break;
                            } else if (result[j] != str2.charAt(t)) {
                                currentEquals = false;
                                break;
                            }
                        }
                    }
                    if (currentEquals) {
                        // Check if there are remaining positions in the substring
                        if (i + m - 1 <= pos) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (valid) {
                    result[pos] = c;
                    break;
                }
            }
            if (result[pos] == '\0') {
                return "";
            }
        }

        return new String(result);
    }
}
